The present invention relates generally to flash memory systems and techniques for efficiently locating meta-data structures on flash-based storage devices.
Flash memory technology is an electrically rewritable nonvolatile digital memory medium. Flash memory cells typically support write operations, read operations, and erase operations. As flash memory technology has evolved, opportunities in a variety of applications have become possible. In particular, flash memory implementations that emulate the mass storage function of conventional rotating magnetic media, e.g., a hard disk drive or a floppy disk drive, coupled to a host computer system or other host digital system have gained wide acceptance.
However, there are some drawbacks commonly found in flash memory devices. In order to achieve equal wear of memory cells in flash memory devices (e.g., NAND-based flash memory device), data to be written to a logical block address (LBA) is usually written to a different address in the Flash chip, namely the physical block address (PBA). The mapping between LBA-to-PBA is maintained by the Flash controller. Further, as erasing a block takes a significant amount of time, this is preferably done in a background task which replenishes a free block queue. Write requests then take blocks from this free block queue. In order to hide this complexity, a flash translation layer (FTL) is utilized. The FTL emulates a block device and allows the operating system to treat flash memory like any other block storage device, hence remaining ignorant of the flash devices characteristics. The implementation of a FTL is very dependent on the application area. The algorithms used in low-cost memory sticks for instance are very rudimentary whereas those in enterprise solid-state devices (SSDs) have to be rather sophisticated in order to ensure the demanded reliability.
A commonly used technique to implement a FTL is based on log-structured file systems and arrays. Mendel Rosenblum and John K. Ousterhout, The Design and Implementation of a Log-Structured File System, ACM Transaction on Computer Systems, 1992, as well as Jai Menon, “A Performance Comparison of RAID-5 and Log-Structured Arrays”, Proc. Of 4th, IEEE Symposium on High Performance Distributed Computing 1995 provide detailed descriptions of such systems and arrays. Log-structured file systems and arrays have been introduced to group I/O operations and improve performance as they write new as well as updated data to new locations instead of writing it in place. During boot time, the LBA-to-PBA mapping has to be restored from the log-structured array which can be achieved by starting with the last checkpoint being written and reading all necessary data structures pointed to from this checkpoint. Current implementations do this by scanning the Flash memory at boot time. However, with increasing capacity of SSDs this can be extremely inefficient and time consuming. Current most advanced SSDs, such as, for example, the STec Zeus support sustained sequential read at 220 MB/s and have up to about 512 GB LBA capacity with a spare factor of 0.4. The NAND Flash storage drive from FusionIO has a sequential read performance of about 610 MB/s and generally a maximum capacity of 320 GB. If the raw capacity grows to 2 TB and assuming a sustained sequential read performance of 610 MB/s, it would take almost one hour to read the whole data from disk.
If checkpoint meta-data is being written block-aligned, i.e., checkpoint meta-data can only reside in the first page of a block, given a block size of 64 pages this process still takes almost one minute. This might be justifiable in an enterprise storage system but not in a desktop SSD. Another possibility to avoid scanning the whole Flash memory would be to store the LBA-to-PBA mapping information on a dedicated part of the Flash memory. However, depending on the workload, the region containing the LBA-to-PBA mapping might wear out much faster than the rest of the device. This would lead to an unnecessary early failure of the device and is therefore not desirable.